package 中等.贪心思想;

/**
 * 给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：
 * nums.length == n
 * nums[i] 是 正整数 ，其中 0 <= i < n
 * abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
 * nums 中所有元素之和不超过 maxSum
 * nums[index] 的值被 最大化
 * 返回你所构造的数组中的 nums[index] 。
 * 注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array
 */
public class 有界数组中指定下标处的最大值_1802 {

    public static void main(String[] args) {

        System.out.println(new 有界数组中指定下标处的最大值_1802().maxValue(6, 1, 10));

    }


    /**
     * 贪心+二分查找
     * 想要使得 nums[index] 尽可能的大，那么其周围的值需要尽可能的小
     * 从 index 向两边递减，差值为 1 ，由于需要正整数，最多递减到 1
     * 可以使用二分查找枚举答案
     */
    public int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum;
        int target = 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long sum = mid;
            sum += sum(index, mid - 1);
            sum += sum(n - index - 1, mid - 1);
            if (sum <= maxSum) {
                target = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return target;
    }

    // 计算count个数，最大值是 max，后面的数逐渐-1，到1之后不再变化的和
    // 例如：count=5，max=3，32111
    private long sum(int count, int max) {
        long sum = 0, n = Math.min(count, max);

        sum += max * n - n * (n - 1) / 2;

        sum += count - n;
        return sum;
    }

}
